package developer.算法.回溯.括号生成;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/4/1 17:25
 * @description 相关标签
 * 相关企业
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：["()"]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 8
 */
public class KuoHaoShengCheng {

    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        List<String> strings = solution.generateParenthesis(3);
        strings.forEach(System.out::println);
    }

    static class Solution4 {
        private List<String> result;

        public List<String> generateParenthesis(int n) {
            result = new ArrayList<>();
            dfs(new StringBuilder(), n, 0, 0);
            return result;
        }

        private void dfs(
                StringBuilder stringBuilder,
                int max,
                int open,
                int close
        ) {
            if (stringBuilder.length() == max * 2) {
                result.add(stringBuilder.toString());
                return;
            }
            if (open < max) {
                stringBuilder.append("(");
                dfs(stringBuilder, max, open + 1, close);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
            if (close < open) {
                stringBuilder.append(")");
                dfs(stringBuilder, max, open, close + 1);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }


    static class Solution3 {
        private List<String> result;

        public List<String> generateParenthesis(int n) {
            result = new ArrayList<>();
            dfs(n, new StringBuilder(), 0, 0);
            return result;
        }

        public void dfs(int max, StringBuilder current, int open, int close) {
            if (current.length() == max * 2) {
                result.add(current.toString());
                return;
            }

            if (open < max) {
                current.append("(");
                dfs(max, current, open + 1, close);
                current.deleteCharAt(current.length() - 1);
            }

            if (close < open) {
                current.append(")");
                dfs(max, current, open, close + 1);
                current.deleteCharAt(current.length() - 1);
            }
        }
    }

    static class Solution {

        private List<String> result;


        public List<String> generateParenthesis(int n) {
            result = new ArrayList<>();
            dfs(n, 0, 0, new StringBuilder());
            return result;
        }

        /**
         * 通过max来限定 左
         * 通过左来限定右
         * 回溯思想
         *
         * @param max
         * @param open
         * @param close
         * @param current
         */
        private void dfs(int max, int open, int close, StringBuilder current) {
            if (current.length() == max * 2) {
                result.add(current.toString());
                return;
            }

            if (open < max) {
                current.append("(");
                dfs(max, open + 1, close, current);
                current.deleteCharAt(current.length() - 1);
            }

            if (close < open) {

                current.append(")");
                dfs(max, open, close + 1, current);
                current.deleteCharAt(current.length() - 1);
            }
        }


    }


    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/generate-parentheses/solutions/192912/gua-hao-sheng-cheng-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class SolutionOfficial {
        public List<String> generateParenthesis(int n) {
            List<String> ans = new ArrayList<String>();
            backtrack(ans, new StringBuilder(), 0, 0, n);
            return ans;
        }

        public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
            if (cur.length() == max * 2) {
                ans.add(cur.toString());
                return;
            }
            if (open < max) {
                cur.append('(');
                backtrack(ans, cur, open + 1, close, max);
                cur.deleteCharAt(cur.length() - 1);
            }
            if (close < open) {
                cur.append(')');
                backtrack(ans, cur, open, close + 1, max);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }


}
